|
The vehicle routing problem (VRP) is a combinatorial optimization and integer programming problem which asks "What is the optimal set of routes for a fleet of vehicles to traverse in order to deliver to a given set of customers?". It generalises the well-known Travelling Salesman Problem (TSP). It first appeared in a paper by George Dantzig and John Ramser in 1959, in which first algorithmic approach was written and was applied to petrol deliveries. Often, the context is that of delivering goods located at a central depot to customers who have placed orders for such goods. The objective of the VRP is to minimize the total route cost. In 1964, Clarke and Wright improved on Dantzig and Ramser's approach using an effective greedy approach called the savings algorithm. Determining the optimal solution is an NP-hard problem in combinatorial optimization, so the size of problems that can be solved optimally is limited . The commercial solvers therefore tend to use heuristics due to the size of real world VRPs and the frequency that they may have to be solved. The VRP has many obvious applications in industry. In fact the use of computer optimisation programs can give savings of 5% to a company as transportation is usually a significant component of the cost of a product (10%) - indeed the transportation sector makes up 10% of the EU's GDP. Consequently, any savings created by the VRP, even less than 5%, are significant.〔 == Setting up the problem == The VRP concerns the service of a delivery company. How things are delivered from one or more ''depots'' which has a given set of home ''vehicles'' and operated by a set of ''drivers'' who can move on a given ''road network'' to a set of ''customers''. It asks for a determination of a set of ''routes'', ''S'', (one route for each vehicle that must start and finish at its own depot) such that all customers' requirements and operational constraints are satisfied and the ''global transportation cost'' is minimised. This cost may be monetary, distance or otherwise.〔 The road network can be described using a graph where the arcs are roads and vertices are junctions between them. The arcs may be directed or undirected due to the possible presence of one way streets or different costs in each direction. Each arc has an associated cost which is generally its length or travel time which may be dependent on vehicle type.〔 To know the global cost of each route, the travel cost and the travel time between each customer and the depot must be known. To do this our original graph is transformed into one where the vertices are the customers and depot and the arcs are the roads between them. The cost on each arc is the lowest cost between the two points on the original road network. This is easy to do as shortest path problems are relatively easy to solve. This transforms the sparse original graph into a complete graph. For each pair of vertices ''i'' and ''j'', there exists an arc ''(i,j)'' of the complete graph whose cost is written as and is defined to be the cost of shortest path from ''i'' to ''j''. The travel time is the sum of the travel times of the arcs on the shortest path from ''i'' to ''j'' on the original road graph. Sometimes it is impossible to satisfy all of a customer's demands and in such cases solvers may reduce some customers' demands or leave some customers unserved. To deal with these situations a priority variable for each customer can be introduced or associated penalties for the partial or lack of service for each customer given 〔 The objective function of a VRP can be very different depending on the particular application of the result but a few of the more common objectives are:〔 *Minimise the global transportation cost based on the global distance travelled as well as the fixed costs associated with the used vehicles and drivers *Minimise the number of vehicles needed to serve all customers *Least variation in travel time and vehicle load *Minimise penalties for low quality service 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Vehicle routing problem」の詳細全文を読む スポンサード リンク
|